17D - Notepad - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;

const int mx=200005;

typedef long long ll;

ll pow(ll a,ll b,ll m)
{
    ll ans=1ll;
    while(b)
    {
        if(b&1ll) ans=(ans*a)%m;
        a=(a*a)%m;
        b=b>>1ll;
    }
    return (ans);
}

/// totient function
ll phi(ll n)
{
    ll result = n;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;

    return result;
}

int main()

{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll c,Phi;
    string s1,s2;

    cin>>s1>>s2>>c;

    Phi=c;
    ll b=0ll;
    ll n_1=0ll;

    /// finding b%c
    for(int i=0;i<(int)s1.size();i++)
    {
        b=b*10+(s1[i]-'0');
        b%=c;
    }
    /// make string of n-1
    for(int i=(int)s2.size()-1;i>=0;i--)
    {
        if(s2[i]=='0') s2[i]='9';
        else
        {
            s2[i]--;
            break;
        }
    }

    Phi=phi(c);
    bool flag=0;

    /// taking number (n-1)
    for(int i=0;i<(int)s2.size();i++)
    {
        n_1=n_1*10+(s2[i]-'0');
        if(n_1>=Phi) flag=1;
        n_1%=Phi;
    }

    if(flag) n_1+=Phi;
    ll ans=((b-1ll)*pow(b,n_1,c))%c;
    if(ans<0) ans=(ans+c)%c;

    if(ans) cout<<ans<<endl;
    else cout<<c<<endl;

	return 0;
}